// ==============================================================
//
//  Copyright (c) 1999-2002 by Alex Vinokur.  This work and all works
//  derived from it may be copied and modified without any
//  restrictions other than that a copy of this copyright notice
//  must be included in any copy of this work or any derived work.
//
// ==============================================================

///////////////////////////////////////

#ifndef classes_H
#define classes_H

///////////////////////////////////////

static char id_classes_H[] = "@(#)## n-ary Huffman Template Algorithm ## Author : Alex Vinokur ## "__FILE__;

// ##############################################################
// =================================
//  n-ary Huffman Template Algorithm
// =================================
//
//  FILE : classes.h
//
//  AUTHOR : Alex Vinokur
//
//  DESCRIPTION :
//         Definition of the following template classes :
//         ----------------------------------------------
//         - Cell                         <SYMBOL, WEIGHT>
//         - Node                         <SYMBOL, WEIGHT>
//         - InternalNode                 <SYMBOL, WEIGHT>
//         - TerminalNode                 <SYMBOL, WEIGHT>
//         - BasicHuffmanTree             <SYMBOL, WEIGHT, ARY>
//         - LoadedHuffmanTree            <SYMBOL, WEIGHT, ARY>
//         - DriedHuffmanTree             <WEIGHT, ARY>
//         ----------------------------------------------
//
//         Definition and implementation of the following template classes :
//         ----------------------------------------------
//         - lessNodesCompare             <SYMBOL, WEIGHT>
//         - lessNodesCorrectingCompare01 <SYMBOL, WEIGHT>
//         - lessNodesCorrectingCompare02 <SYMBOL, WEIGHT>
//         - lessCellsCompare             <SYMBOL, WEIGHT>
//         - lessVectorsAlterCompare      <T>
//         ----------------------------------------------
//
// ##############################################################

// ======================
#include "service.h"
// ======================

// #######################################################
// ##### PART : DEFINES & CONSTANTS ######################
// #######################################################

// #define       SHOW_HUFFMAN_PROCESS_STATUS


// #######################################################
// ##### PART : DECLARATIONS #############################
// #######################################################

template <typename SYMBOL, typename WEIGHT>
class Cell;

template <typename SYMBOL, typename WEIGHT>
class Node;

template <typename SYMBOL, typename WEIGHT>
class InternalNode ;

template <typename SYMBOL, typename WEIGHT>
class TerminalNode ;

template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
class BasicHuffmanTree;

template <typename SYMBOL, typename WEIGHT, unsigned int ARY = 2>
class LoadedHuffmanTree;

template <typename WEIGHT, unsigned int ARY = 2>
class DriedHuffmanTree;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCompare;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare01;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare02;

template <typename SYMBOL, typename WEIGHT>
class lessCellsCompare;

template <typename T1>
class lessVectorsAlterCompare;




// #######################################################
// ##### PART : template class Cell ######################
// ############ Definition ###############################
// #######################################################

// ----------- template class Cell -----------
template <typename SYMBOL, typename WEIGHT>
class Cell
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;

friend class TerminalNode<SYMBOL, WEIGHT>;
friend class lessCellsCompare<SYMBOL, WEIGHT>;
friend istream& operator>> <SYMBOL, WEIGHT> (istream &str_o, Cell<SYMBOL, WEIGHT>& instance_i);
friend ostream& operator<< <SYMBOL, WEIGHT> (ostream &str_o, const Cell<SYMBOL, WEIGHT>& instance_i);

        private :
                SYMBOL  data_symbol_;
                WEIGHT  data_weight_;
                unsigned int    symbol_original_index_;
                vector<CODE>    symbol_path_;
        protected :

        public :
                Cell () {}
                Cell (
                        const SYMBOL&   data_symbol_i,
                        const WEIGHT&   data_weight_i,
                        unsigned int    symbol_original_index_i = UINT_MAX
                        );
                virtual ~Cell () {}

};




// #######################################################
// ##### PART : template class Node ######################
// ############ Definition ###############################
// #######################################################

// ----------- template class Node -----------
template <typename SYMBOL, typename WEIGHT>
class Node
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;

friend class InternalNode<SYMBOL, WEIGHT>;
friend class lessNodesCompare<SYMBOL, WEIGHT>;
friend class lessNodesCorrectingCompare01<SYMBOL, WEIGHT>;
friend class lessNodesCorrectingCompare02<SYMBOL, WEIGHT>;
friend ostream& operator<< <SYMBOL, WEIGHT> (ostream &str_o, const Node<SYMBOL, WEIGHT>& instance_i);

typedef map<SYMBOL, WEIGHT, less<SYMBOL> > Node_MAP_SYMBOLS;

        private :
        protected :
                Node_MAP_SYMBOLS        mapSymbols_;
                WEIGHT                  weight_;
                bool                    is_TerminalNode_;
                int                     absorbtion_stage_;
                int                     creation_stage_;

        public :
                Node () {weight_ = WEIGHT (); absorbtion_stage_ = -2; creation_stage_ = -1;}
                virtual ~Node () {}
};




// #######################################################
// ##### PART : template class InternalNode ##############
// ############ Definition ###############################
// #######################################################

// ----------- template class InternalNode -----------
template <typename SYMBOL, typename WEIGHT>
class InternalNode : public Node<SYMBOL, WEIGHT>
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;
        private :
                vector<Node<SYMBOL, WEIGHT>*>   arc_;
        protected :
                void addNode (Node<SYMBOL, WEIGHT> const *  const ptr2_i);
        public :
                InternalNode () {is_TerminalNode_ = false;}
                ~InternalNode () {}
};




// #######################################################
// ##### PART : template class TerminalNode ##############
// ############ Definition ###############################
// #######################################################

// ----------- template class TerminalNode -----------
template <typename SYMBOL, typename WEIGHT>
class TerminalNode : public Node<SYMBOL, WEIGHT>
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;
        private :

        protected :
        public :
                TerminalNode () {is_TerminalNode_ = true;}
                TerminalNode (const Cell<SYMBOL, WEIGHT>& cell_i);
                ~TerminalNode () {}
};



// #######################################################
// ##### PART : template class less... ###################
// #######################################################

// #######################################################
// ----------- template class lessNodesCompare -----------
template <typename SYMBOL, typename WEIGHT>
class lessNodesCompare
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return (left_i->weight_ < right_i->weight_);
        }
};


// #######################################################
// ------- template class lessNodesCorrectingCompare01 -----
template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare01
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return ((left_i->weight_ == right_i->weight_) ? (!(left_i->is_TerminalNode_)) : (left_i->weight_ < right_i->weight_));
        }
};



// #######################################################
// ------- template class lessNodesCorrectingCompare02 -----
template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare02
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return ((left_i->is_TerminalNode_ == right_i->is_TerminalNode_) ? (left_i->weight_ < right_i->weight_) : (!(left_i->is_TerminalNode_)));
        }
};


// #######################################################
// ----------- template class lessCellsCompare -----------
template <typename SYMBOL, typename WEIGHT>
class lessCellsCompare
{
public:
        bool operator()(
                        const Cell<SYMBOL, WEIGHT>& left_i,
                        const Cell<SYMBOL, WEIGHT>& right_i
                        )
        {

                return (left_i.data_weight_ < right_i.data_weight_);
        }
};




// #######################################################
// ----------- template class lessVectorsAlterCompare -----------
template <typename T1>
class lessVectorsAlterCompare
{
public:
        bool operator()(
                        const vector<T1>&       left_i,
                        const vector<T1>&       right_i
                        )
        {
                if (left_i.size () < right_i.size ())
                {
                        return true;
                }

                if (left_i.size () > right_i.size ())
                {
                        return false;
                }

                return (left_i < right_i);
        }
};




// #######################################################
// ##### PART : template class BasicHuffmanTree ##########
// ############ Definition ###############################
// #######################################################


// #######################################################
// ----------- template class BasicHuffmanTree -----------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
class BasicHuffmanTree
{
typedef map<SYMBOL, Cell<SYMBOL, WEIGHT>, less<SYMBOL> > Tree_MAP_SYMBOLS;
typedef map<vector<CODE>, SYMBOL, less<vector<CODE> > > Tree_MAP_HUFFMAN_DECODING;

        private :
                Tree_MAP_SYMBOLS                mapAlphabet_;
                Tree_MAP_HUFFMAN_DECODING       mapHuffmanCodes_;
                InternalNode<SYMBOL, WEIGHT>    rootNode_;
                vector<vector<CODE> >           vectorHuffmanCodes_;


                void    createAllTerminalNodes (
                                const vector<Cell<SYMBOL, WEIGHT> >&    data_vector_i,
                                vector<Node<SYMBOL, WEIGHT>*>&          vectorHuffmanProcess_i
                                );
                void    createInternalNode (
                                vector<Node<SYMBOL, WEIGHT>*>&          vectorHuffmanProcess_i,
                                int                                     cur_stage_i
                                );

                void    createHuffmanTree (
                                vector<Node<SYMBOL, WEIGHT>*>&          vectorHuffmanProcess_i
                                );

                void    doBeautyTreatment (
                                vector<Node<SYMBOL, WEIGHT>*>&          vectorHuffmanProcess_i
                                );


                void    storeHuffmanCodes ();


                bool            encodeOneSymbol (
                                        const SYMBOL&   symbol_i,
                                        vector<CODE>&   path_o)
                                        const;


                bool            decodeOneSymbol (
                                        const vector<CODE>&     encoded_msg_i,
                                        unsigned int&           cur_start_position_io,
                                        unsigned int&           cur_symbol_number_io,
                                        vector<CODE>&           cur_symbol_code_o,
                                        SYMBOL&                 cur_symbol_value_o
                                        ) const;

                bool            decodeOneSymbol (
                                        const vector<CODE>&     encoded_symbol_code_i,
                                        SYMBOL&                 decoded_symbol_value_o
                                        ) const;

                bool            testAllCodes (bool show_i = false) const;

                void            showHuffmanProcessStatus (
                                        vector<Node<SYMBOL, WEIGHT>*>&  vectorHuffmanProcess_i,
                                        int                             cur_stage_i = 0,
                                        const string&                   msg_i = string ()
                                        ) const;

                static void     print_show_title_S (
                                        const string&   spaces_offset_i,
                                        unsigned int    setw_symbol_i,
                                        const string&   symbol_title_i,
                                        unsigned int    setw_weight_i,
                                        const string&   weight_title_i,
                                        const string&   code_title_i
                                        );

                static void     print_show_line_S (
                                        const string&   spaces_offset_i,
                                        unsigned int    setw_symbol_i,
                                        const SYMBOL&   symbol_i,
                                        unsigned int    setw_weight_i,
                                        const WEIGHT&   weight_i,
                                        const vector<CODE>&     path_i
                                        );


                bool            knowSymbolWeight (
                                        const SYMBOL&   symbol_i,
                                        WEIGHT&         weight_o
                                        ) const;

                bool            knowCodeSymbol (
                                        const vector<CODE>&     path_i,
                                        SYMBOL&                 symbol_o
                                        ) const;

                WEIGHT          getWeightsSum () const;

                WEIGHT          getAverageWeight () const
                {
                        return (getWeightsSum ()/getAlphabetSize ());
                }

                unsigned int    getCodeAry () const {return ARY;}

                unsigned int    getLongestSymbolSize () const;

                unsigned int    getAlphabetSize () const
                {
                        return vectorHuffmanCodes_.size ();
                }

                unsigned int    getShortestCodeSize () const
                {
                        return vectorHuffmanCodes_[0].size ();
                }

                unsigned int    getLongestCodeSize () const
                {
                        return vectorHuffmanCodes_[vectorHuffmanCodes_.size () - 1].size ();
                }

                unsigned int    getCodeSizesSum () const;

                float           getAverageCodeSize () const
                {
                        return (static_cast<float>(getCodeSizesSum ())/static_cast<float>(getAlphabetSize ()));
                }

                WEIGHT          getAverageWeightedCodeSize () const
                {
                        return (getWeightedCodeSizesSum ())/(getAlphabetSize ());
                }

                WEIGHT          getWeightedCodeSizesSum () const;

        protected :
                void    doBasicHuffmanTree (
                                const vector<Cell<SYMBOL, WEIGHT> >& data_vector_i
                                );

                BasicHuffmanTree () {}

                BasicHuffmanTree (
                        const vector<Cell<SYMBOL, WEIGHT> >& data_vector_i
                        );

                BasicHuffmanTree (const string& data_file_name_i);

                virtual ~BasicHuffmanTree () {}

        public :
                bool            encodeMsg (
                                        const vector<SYMBOL>&   source_msg_i,
                                        vector<CODE>&           encoded_msg_o)
                                        const;

                bool            encodeMsg (
                                        const basic_string<SYMBOL>&     source_msg_i,
                                        string&                         encoded_msg_o)
                                        const;

                bool            decodeMsg (
                                        const vector<CODE>&     encoded_msg_i,
                                        vector<SYMBOL>&         decoded_msg_o
                                        ) const;

                bool            decodeMsg (
                                        const string&                   encoded_msg_i,
                                        basic_string<SYMBOL>&           decoded_msg_o
                                        ) const;


                void            showAll (const string& msg_i = string ()) const;
};





// #######################################################
// ##### PART : template class LoadedHuffmanTree #########
// ############ Definition ###############################
// #######################################################

// ----------- template class LoadedHuffmanTree -----------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
class LoadedHuffmanTree : public BasicHuffmanTree<SYMBOL, WEIGHT, ARY>
{

        public :
                LoadedHuffmanTree () : BasicHuffmanTree<SYMBOL, WEIGHT, ARY> () {}

                LoadedHuffmanTree (
                        const vector<Cell<SYMBOL, WEIGHT> >& data_vector_i
                        )
                        :
                        BasicHuffmanTree<SYMBOL, WEIGHT, ARY> (data_vector_i) {}

                LoadedHuffmanTree (const string& data_file_name_i)
                : BasicHuffmanTree<SYMBOL, WEIGHT, ARY> (data_file_name_i) {}

                ~LoadedHuffmanTree () {}
};





// #######################################################
// ##### PART : template class DriedHuffmanTree ##########
// ############ Definition ###############################
// #######################################################

// ----------- template class DriedHuffmanTree -----------
template <typename WEIGHT, unsigned int ARY>
class DriedHuffmanTree : public BasicHuffmanTree<string, WEIGHT, ARY>
{
        private :

                void    doDriedHuffmanTree (
                                const vector<WEIGHT>& weight_vector_i
                                );
        protected :
        public :

                DriedHuffmanTree (
                                const vector<WEIGHT>& weight_vector_i
                                );
                DriedHuffmanTree (const string& weights_file_name_i);

                ~DriedHuffmanTree () {}
};


#endif	// classes_H

// #######################################################
// ################ END OF FILE ##########################
// #######################################################

